//为了不在赎金信中暴露字迹，从杂志上搜索各个需要的字母，组成单词来表达意思。 
//
// 给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串，判断 ransomNote 能不能由 magazines 里面的字符
//构成。 
//
// 如果可以构成，返回 true ；否则返回 false 。 
//
// magazine 中的每个字符只能在 ransomNote 中使用一次。 
//
// 
//
// 示例 1： 
//
// 
//输入：ransomNote = "a", magazine = "b"
//输出：false
// 
//
// 示例 2： 
//
// 
//输入：ransomNote = "aa", magazine = "ab"
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：ransomNote = "aa", magazine = "aab"
//输出：true
// 
//
// 
//
// 提示： 
//
// 
// 1 <= ransomNote.length, magazine.length <= 105 
// ransomNote 和 magazine 由小写英文字母组成 
// 
// Related Topics 哈希表 字符串 计数 
// 👍 201 👎 0

package leetcode.editor.cn;

/**
 * [383]赎金信
 */
public class RansomNote {
    public static void main(String[] args) {
        Solution solution = new RansomNote().new Solution();
        System.out.println(solution.canConstruct("aab", "baa"));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean canConstruct(String ransomNoste, String magazine) {
        // 两种方法，定义一个数组或者map   一个哦
        int[] array = new int[26];
        int i;
        int circle = 0;
        for (i = 0; i < ransomNoste.length(); i++) {
            if (array[ransomNoste.charAt(i) - 'a'] != 0) {
                array[ransomNoste.charAt(i) - 'a'] -= 1;
            } else {
                // 及时终止掉，数据量大实话，速度快。
                while (array[ransomNoste.charAt(i) - 'a'] == 0) {
                    if (circle == magazine.length()) {
                        return false;
                    }
                    array[magazine.charAt(circle) - 'a'] = array[magazine.charAt(circle) - 'a'] + 1;
                    circle++;
                }
                array[ransomNoste.charAt(i) - 'a'] = 0;
            }
        }
        return i == ransomNoste.length();
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}